/*
 * @lc app=leetcode.cn id=765 lang=java
 *
 * [765] 情侣牵手
 */

// @lc code=start
class Solution {
    //这个思路真的抽象，好难想到啊
    public int minSwapsCouples(int[] row) {
        UnionFindSet unionFindSet = new UnionFindSet(row.length / 2);//开长为n的并查集
        for (int i = 0; i < row.length; i+=2) {
            unionFindSet.union(row[i] / 2, row[i+1] / 2);
            //代表这两个情侣的位置，如果不一样，就并在一起，表示需要后期交换
            //这部分的原理官方题解已经讲过了，我觉得还是很反直觉的。
        }
        
        return unionFindSet.getCount();
        //并查集求出图中的每个连通分量；对于每个连通分量而言，其大小减 1 就是需要交换的次数。
    }
}

class UnionFindSet {
    int count;//记录交换次数
    int[] f;

    public UnionFindSet(int n) {
        this.count = 0;
        f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }

    public int find(int x) {
        int fx = f[x];
        // 路径压缩
        if (fx != f[fx]) f[x] = find(fx);

        return f[x];
    }

    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);

        if (fx != fy) {//需要并在一起
            f[fx] = fy;
            count++;
        }
    }

    public int getCount() {
        return count;
    }
}

// @lc code=end

